//
// Created by zhouheyu on 17-11-26.
//
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "LRU.h"

#define PAGE_NUM_PER_BLK 64
#define SEC_NUM_PER_PAGR 4
#define SEC_NUM_PER_BLK 256

//自己定义数据块的大小
int blk_num=8192;//大概1个G大小的数据规模

#define CACHE_MAX_ENTRIES 1024*4

int lru_cache_arr[CACHE_MAX_ENTRIES] ;
int clru_cache_arr[CACHE_MAX_ENTRIES] ;
int dlru_cache_arr[CACHE_MAX_ENTRIES] ;

//reset cache state
void reset_cache_stat()
{
    cache_read_num = 0;
    cache_write_num = 0;
}

//计算cache的操作时延
double calculate_delay_cache()
{
    double delay;
    double cache_read_delay=0.0,cache_write_delay=0.0;
    cache_read_delay=(double)CACHE_READ_DELAY*cache_read_num;
    cache_write_delay=(double)CACHE_WRITE_DELAY*cache_write_num;
    delay=cache_read_delay+cache_write_delay;
    reset_cache_stat();
    return delay;
}
//初始化对应统计变量
void InitVariable()
{
    int i;
    cache_max_index=0;
    cache_min_index=0;
    //初始化统计变量
    buffer_cnt=0;
    buffer_hit_cnt=0;
    buffer_miss_cnt=0;
    buffer_write_hit=0;
    buffer_write_miss=0;
    buffer_read_hit=0;
    buffer_read_miss=0;
    physical_read=0;
    physical_write=0;
    //初始化相应的CACHE中间变量
    CACHE_NUM_ENTRIES=0;
    CACHE_CLRU_NUM_ENTRIES=0;
    CACHE_DLRU_NUM_ENTRIES=0;
    //分配内存给NandPage
    NandPage_Num=blk_num*PAGE_NUM_PER_BLK;
    NandPage=(struct page_entry*)malloc(sizeof(struct page_entry)*NandPage_Num);
    if(NandPage==NULL){
        printf("the create Nandpage Memeory is failed\n");
        exit(1);
    }
    memset(NandPage,0xFF,sizeof(struct page_entry)*NandPage_Num);
    for ( i = 0; i <NandPage_Num ; ++i) {
        NandPage[i].cache_age=0;
        NandPage[i].cache_status=0;
        NandPage[i].cache_update=0;
    }
}

void FreeVariable()
{
    //释放对应的内存
    if(NandPage!=NULL)
    {
        free(NandPage);
    }
}

//输出对应的统计结果
void PrintResultStat()
{
    //输出和缓冲区统计相关的信息
    printf("****************************************\n");
    printf("the all buffer req count is %d\n",buffer_cnt);
    printf("the buffer miss count is %d\n",buffer_miss_cnt);
    printf("the hit rate is %f\n",(double)(buffer_cnt-buffer_miss_cnt)/buffer_cnt);
    printf("the buffer read miss count is %d\n",buffer_read_miss);
    printf("the buffer write miss count is %d\n",buffer_write_miss);
    printf("the buffer read hit count is %d\n",buffer_read_hit);
    printf("the buffer write hit count is %d\n",buffer_write_hit);
    printf("the physical read count is %d\n",physical_read);
    printf("the physical write count is %d\n",physical_write);
}

int my_find_cache_max(int *arr,int arrMaxSize)
{
    int i;
    int temp=-1;
    int cache_max=-1;
    for ( i = 0; i <arrMaxSize ; ++i) {
        if (arr[i]!=-1){
            if (NandPage[arr[i]].cache_age>temp){
                temp=NandPage[arr[i]].cache_age;
                cache_max=arr[i];
            }
        }
    }
    return cache_max;
}

//找到数组中索引对应的LPN的age最大或最小
int my_find_cache_min(int *arr,int arrMaxSize)
{
    int i;
    int temp=99999999;
    int cache_min=-1;
    for (i = 0; i <arrMaxSize ; ++i) {
        //attention arr[i]=-1 ,the NandPage[-1] is error
        if(arr[i]!=-1){
            if(NandPage[arr[i]].cache_age<temp){
                temp=NandPage[arr[i]].cache_age;
                cache_min=arr[i];
            }
        }
    }
    return cache_min;
}

//计算数组中非负数个数
int calculate_arr_positive_num(int *arr,int size)
{
    int i;
    int count=0;
    for ( i = 0; i <size ; ++i) {
        if(arr[i]>=0){
            count++;
        }
    }
    return count;
}

int find_free_pos( int *arr, int size)
{
    int i;
    for(i = 0 ; i < size; i++) {
        if(arr[i] == -1) {
            return i;
        }
    }
    printf("shouldnt come here for find_free_pos()");
    exit(1);
    return -1;
}

//从对应的数组中找到对应的数据项，并返回该数据项在数组的中位置
//没有找到对应的数据则返回-1
int search_table(int *arr,int size,int val)
{
    int i;
    for (i = 0; i <size ; ++i) {
        if(arr[i]==val){
            return i;
        }
    }
    return -1;
}

//初始化数组，参考init_arr
void init_my_arr()
{
    int i;
    for( i = 0; i < CACHE_MAX_ENTRIES; i++) {
        lru_cache_arr[i] = -1;
        clru_cache_arr[i] =-1;
        dlru_cache_arr[i] =-1;
    }
}


double CacheManage(unsigned int secno,int scount,int operation)
{
    //定义时延变量
    double delay,flash_delay=0,cache_delay=0;
    int bcount,entry_count;
    unsigned int blkno;
    //定义算法需要使用的中间变量
    int  free_pos=-1;
    int  vicitm_page_index=-1;
    int HitIndex;
    int  cnt=0;
    //页对齐操作
    blkno=secno/4;
    bcount=(secno+scount-1)/4-(secno)/4+1;
    //重置cache_stat相关状态
    reset_cache_stat();
    cnt=bcount;
    while(cnt>0){
        buffer_cnt++;
        HitIndex=FindLPNInCache(blkno);
        if(HitIndex>0){
            //命中lru
            buffer_hit_cnt++;
            UpdateNandPageStat(blkno,operation);
            if(operation==0){
                buffer_write_hit++;
                cache_write_num++;
            }else
            {
                buffer_read_hit++;
                cache_read_num++;
            }

        }else{
            //未命中lru
            buffer_miss_cnt++;
            if(CACHE_NUM_ENTRIES>=CACHE_MAX_ENTRIES){
                //启动剔除操作
                vicitm_page_index=FindVictimInLruCacheArr();
                flash_delay+=DelVictimFromLRU(vicitm_page_index);
            }
            //将新的数据加入到lru
                flash_delay+=AddNewToLRU(blkno,operation);
        }
        cnt--;
        blkno++;
    }
    cache_delay=calculate_delay_cache();
    delay=cache_delay+flash_delay;
    //test point
    printf("the request blkno is %d\tcache_delay is %f flash_delay is %f\n",(blkno-bcount),cache_delay,flash_delay);
    return delay;
}


//判断对应的LPN是否在缓冲区中，如果存在返回在cache_arr中的位置索引,如果不存在则返回-1
int FindLPNInCache(int LPN)
{
    int object;
    //先做一个错误，是否存在LPN超出NandPage的大小
    if(LPN>NandPage_Num)
    {
        printf("the error happenend in FindLPNInCache function\n");
        printf("the LPN:%d over the database volume\n",LPN);
        printf("the NandPage Num is %d\n",NandPage_Num);
        exit(1);
    }
    //通过NandPage的下标快速定位是否存在
    if(NandPage[LPN].cache_status==CACHE_INVALID){
        return -1;
    }
    //下面这部分其实可以砍掉
    object=search_table(lru_cache_arr,CACHE_MAX_ENTRIES,LPN);
    if(object==-1){
        printf("the search table can not find LPN:%d in cache_arr\n",LPN);
        exit(1);
    }
    return object;
}

//命中后修改对应的NandPage的状态,无论命中还是初次加载数据页都需要调用更新NandPage状态
void UpdateNandPageStat(int LPN,int operation)
{
    //先做一个错误，是否存在LPN超出NandPage的大小
    if(LPN>NandPage_Num)
    {
        printf("error happened in UpdateNandPageStat\n");
        printf("the LPN:%d over the database volume\n",LPN);
        printf("the NandPage Num is %d\n",NandPage_Num);
        exit(1);
    }
    NandPage[LPN].cache_age=NandPage[cache_max_index].cache_age+1;
    cache_max_index=LPN;
    NandPage[LPN].cache_status=CACHE_VALID;
    //根据读写类型区别操作
    if (operation == 0) {
        NandPage[LPN].cache_update = 1;
    }
}

//重置对应的NandPage的状态为初始状态的值
void ResetNandPageStat(int LPN)
{
    //先做一个错误，是否存在LPN超出NandPage的大小
    if(LPN>NandPage_Num)
    {
        printf("error happened in ResetPageStat function\n");
        printf("the LPN:%d over the database volume\n",LPN);
        printf("the NandPage Num is %d\n",NandPage_Num);
        exit(1);
    }
    NandPage[LPN].cache_age=0;
    NandPage[LPN].cache_status=CACHE_INVALID;
    NandPage[LPN].cache_update=0;
}

//选择lru_cache_arr中的剔除对象，返回的是lru_cache_arr即将提出的对象的索引
int FindVictimInLruCacheArr()
{
    //做一个错误检测，判断当前的Cache大小计算是否正常
    int L;
    int lru_Victim;
    //计算当前数组中存在多少有效的数据项
    L=calculate_arr_positive_num(lru_cache_arr,CACHE_MAX_ENTRIES);
    if(CACHE_NUM_ENTRIES!=L) {
        printf("CACHE NUM ENTRIES is %d\n",CACHE_NUM_ENTRIES);
        printf("lru list entry number is %d\n",L);
        exit(1);
    }
    //找到对应的最小LPN
    cache_min_index=my_find_cache_min(lru_cache_arr,CACHE_MAX_ENTRIES);
    //找到对应的位置
    lru_Victim=search_table(lru_cache_arr,CACHE_MAX_ENTRIES,cache_min_index);
    //加入错误判读
    if (lru_Victim==-1){
        printf("the search_table find  vicitm of lru_arr error\n");
        printf("the Victim LPN is %d\n",cache_min_index);
        exit(-1);
    }
    return lru_Victim;
}

//剔除lru数组中的剔除对象并重置相应的NandPage，统计对应的物理回写次数,返回读写延迟
double DelVictimFromLRU(int Victim_page_index)
{
    int Victim_LPN;
    double delay=0.0;
    Victim_LPN=lru_cache_arr[Victim_page_index];
    //先做一个错误，是否存在LPN超出NandPage的大小
    if(Victim_LPN>NandPage_Num)
    {
        printf("error happened in DelVicitm function\n");
        printf("the LPN:%d over the database volume\n",Victim_LPN);
        printf("the NandPage Num is %d\n",NandPage_Num);
        exit(1);
    }
    if(NandPage[Victim_LPN].cache_update==1){
        physical_write++;
        //这里可以调用对应的函数计算相应的读写延迟
        delay+=FLASH_WRITE_DELAY;
    }
    //重置对应的NandPage的状态
    ResetNandPageStat(Victim_LPN);
    //从对应的lru数组中删除对应的索引
    lru_cache_arr[Victim_page_index]=-1;
    CACHE_NUM_ENTRIES--;
    //加入错误判断
    if(CACHE_NUM_ENTRIES!=calculate_arr_positive_num(lru_cache_arr,CACHE_MAX_ENTRIES)){
        printf("lru数组中的有效项数和CACHE_NUM_ENTRIES不等\n");
        printf("CACHE_NUM_ENTRIES is %d\n",CACHE_NUM_ENTRIES);
        printf("lru-list number is %d\n",calculate_arr_positive_num(lru_cache_arr,CACHE_NUM_ENTRIES));
        exit(1);
    }

    return delay;
}
//添加新的数据到LRU中返回的是读写延迟
double AddNewToLRU(int LPN,int operation)
{
    double delay=0.0;
    int free_pos=-1;
    //加入错误判断
    if(CACHE_NUM_ENTRIES!=calculate_arr_positive_num(lru_cache_arr,CACHE_MAX_ENTRIES)){
        printf("error happenend in AddNewtoLRU\n");
        printf("lru数组中的有效项数和CACHE_NUM_ENTRIES不等\n");
        printf("CACHE_NUM_ENTRIES is %d\n",CACHE_NUM_ENTRIES);
        printf("lru-list number is %d\n",calculate_arr_positive_num(lru_cache_arr,CACHE_NUM_ENTRIES));
        exit(1);
    }
    //找到数组中空余的位置
    free_pos=find_free_pos(lru_cache_arr,CACHE_MAX_ENTRIES);
    if(free_pos==-1){
        printf("can't find free position for current LPN %d \n",LPN);
        exit(0);
    }
    lru_cache_arr[free_pos]=LPN;
    CACHE_NUM_ENTRIES++;
    //计算相应的时延
    delay+=FLASH_READ_DELAY;
    //更新对应的NandPage的状态
    UpdateNandPageStat(LPN,operation);
    if(operation==0){
        buffer_write_miss++;
    }else{
        buffer_read_miss++;
    }
    return delay;
}

